#coding:utf8
#最简单的方法就是用库拉
#也可以用dfs深度优先算法。
'''
123
132
213
231
312
321
'''
class Solution(object):
    def permute(self, nums):
        import itertools
        return map(list, itertools.permutations(nums))

s = Solution()
print s.permute([1,2,3])

class Solution2(object):
    def permute(self, nums):
        return [[n] + p
            for i, n in enumerate(nums)
            for p in self.permute(nums[:i] + nums[i+1:])] or [[]]

s2 = Solution2()
print s2.permute([1,2,3])


class Solution3(object):
    def permute(self,nums):
        res = []
        self.dfs(nums,[],res)
        return res
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            return
        for i,n in enumerate(nums):
            self.dfs(nums[:i]+nums[i+1:],path+[n],res)

s3 = Solution3()
print s3.permute([1,2,3])
